W3. Предикаты, кванторы и законы де Моргана (De Morgan’s laws)

Автор

Zakhar Podyakov

Дата публикации

18 сентября 2025 г.

Quiz | Flashcards

1. Кратко

1.1 От высказываний к предикатам

В логике высказывание (proposition) — повествовательное предложение, однозначно истинное или ложное. Например: «число 4 чётно» — истинное высказывание. Часто нужны утверждения, истинность которых зависит от значения переменной, например «\(x\) чётно».

Здесь появляются предикаты (predicates): предикат — это высказывание с одной или несколькими переменными, которое становится высказыванием после подстановки конкретных значений. Предикат «\(x\) чётно» можно записать как \(P(x)\); при \(x=4\) получаем истинное высказывание \(P(4)\). Множество допустимых значений переменной называют областью (domain); истинность предиката существенно зависит от выбранной области.

1.2 Кванторы: обобщение предикатов

Кванторы (quantifiers) позволяют формулировать утверждения о предикате сразу на всей области, не перечисляя каждое значение. Два основных квантора:

1.2.1 Квантор всеобщности (\(\forall\), universal quantifier)

Символ \(\forall\) читается как «для всех» / «для любого». Запись \(\forall x\, P(x)\) означает, что \(P(x)\) истинно для каждого элемента \(x\) области.

  • Пример: если область — все чётные числа, то \(\forall x\,(\text{«}x\text{ делится на 2»})\) истинно.
  • Связь с логикой: на конечной области \(\{x_1,\dots,x_n\}\) формула \(\forall x\,P(x)\) эквивалентна конъюнкции \(P(x_1)\land\dots\land P(x_n)\). Квантор всеобщности истинен только если истинны все слагаемые.
1.2.2 Квантор существования (\(\exists\), existential quantifier)

Символ \(\exists\) читается как «существует» / «для некоторого». Запись \(\exists x\,P(x)\) означает, что хотя бы для одного \(x\) в области \(P(x)\) истинно.

  • Пример: на области целых чисел \(\exists x\,(x^2=9)\) истинно (например, \(x=3\) или \(x=-3\)).
  • Связь с логикой: на конечной области \(\exists x\,P(x)\) эквивалентно дизъюнкции \(P(x_1)\lor\dots\lor P(x_n)\). Достаточно одного истинного слагаемого.
1.3 Свободные и связанные переменные

Переменная может быть связанной (bound) или свободной (free).

  • Связанная — входит в область действия квантора; в \(\forall x\,(x>y)\) переменная \(x\) связана квантором \(\forall\).
  • Свободная — не связана квантором; в том же примере \(y\) свободна.

Формула без свободных переменных — высказывание (при заданной области истинность определена). Со свободными переменными — по сути предикат: значение зависит от подстановки свободных переменных.

1.4 Интерпретации и контрпримеры
  • Интерпретация (interpretation) — выбор области и значений предикатов, при котором формула становится истинной (TRUE).
  • Контрпример (counterexample) — интерпретация, при которой формула ложна (FALSE). Для опровержения \(\forall x\,(\text{«}x\text{ нечётно»})\) на целых достаточно одного контрпримера, например \(x=2\).
1.5 Законы де Моргана для кванторов (De Morgan’s laws for quantifiers)

Эти законы связывают отрицание с кванторами: отрицание «выносится внутрь» с сменой квантора.

  1. Отрицание \(\forall\): «не верно, что для всех \(x\) истинно \(P(x)\)» эквивалентно «существует \(x\), для которого ложно \(P(x)\)». \[ \neg \forall x P(x) \equiv \exists x \neg P(x) \]
  2. Отрицание \(\exists\): «не верно, что существует \(x\) с \(P(x)\)» эквивалентно «для всех \(x\) ложно \(P(x)\)». \[ \neg \exists x P(x) \equiv \forall x \neg P(x) \]
1.6 Свойства кванторов

Кванторы по-разному согласуются с связками AND (\(\&\)) и OR (\(\lor\)).

  • \(\forall\) и конъюнкция: \(\forall x\,(P(x)\land R(x)) \equiv \forall x\,P(x) \land \forall x\,R(x)\).
  • \(\exists\) и дизъюнкция: \(\exists x\,(P(x)\lor R(x)) \equiv \exists x\,P(x) \lor \exists x\,R(x)\).
  • Важно: \(\forall\) нельзя распределять по \(\lor\) «по частям»; \(\exists\) — по \(\&\) аналогично.
1.7 Вложенные кванторы

Кванторы могут быть вложены, например \(\forall x\,\exists y\,(x+y=0)\); порядок кванторов критичен.

  • Одинаковые кванторы: порядок не важен: \(\forall x\forall y\,P(x,y)\equiv\forall y\forall x\,P(x,y)\), аналогично для \(\exists\).
  • Разные кванторы: порядок меняет смысл; в частности, \[ \exists x\forall y\,P(x,y) \rightarrow \forall y\exists x\,P(x,y) \] импликация в эту сторону верна, обратная — нет. Например, для \(P(x,y)\) вида «\(x\ge y\)» на \(\mathbb{N}\): \(\exists x\forall y\) ложно, а \(\forall y\exists x\) истинно (можно взять \(x=y\) или \(x=y+1\)).
1.8 Особые кванторы
  • Единственность (\(\exists!\), uniqueness quantifier): \(\exists!x\,P(x)\) — «существует ровно один \(x\) такой, что \(P(x)\)».
  • Ограниченные кванторы (restricted quantifiers):
    • Ограниченный \(\forall\): запись \(\forall x>0,\,P(x)\) формально: \(\forall x\,(x>0 \rightarrow P(x))\).
    • Ограниченный \(\exists\): \(\exists x>0,\,P(x)\) формально: \(\exists x\,(x>0 \land P(x))\).

2. Определения

  • Множество (set): неупорядоченная совокупность различных элементов.
  • Высказывание (proposition): предложение, однозначно истинное или ложное.
  • Предикат (predicate): высказывание с переменными, которое становится высказыванием после подстановки значений из области.
  • Область (domain): множество допустимых значений переменной предиката.
  • Квантор \(\forall\) (universal quantifier): «для всех» / «для каждого».
  • Квантор \(\exists\) (existential quantifier): «существует» / «для некоторого».
  • Связанная переменная (bound variable): под действием квантора.
  • Свободная переменная (free variable): не связана квантором.
  • Интерпретация (interpretation): область и значения предикатов, делающие формулу истинной (TRUE).
  • Контрпример (counterexample): интерпретация, делающая формулу ложной (FALSE).

3. Формулы

  • Закон де Моргана для \(\forall\): \(\neg \forall x P(x) \equiv \exists x \neg P(x)\)
  • Закон де Моргана для \(\exists\): \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)
  • Ограниченный \(\forall\): \(∀x∈A P(x) ≡ ∀x (A(x) → P(x))\)
  • Ограниченный \(\exists\): \(∃x∈A P(x) ≡ ∃x (A(x) ∧ P(x))\)

4. Примеры

4.1. Перевод формулы логики предикатов (Лаба 3, Задание 1)

Пусть \(P(x)\) означает «\(x\) посетил Иннополис» (область — все студенты). Переведите формулу \(\neg\forall x\,P(x)\) на естественный английский.

Показать решение
  1. Главная операция: перед нами отрицание (\(\neg\)) утверждения с квантором всеобщности.
  2. Квантор и предикат: \(\forall x\,P(x)\) — «каждый студент посетил Иннополис».
  3. Отрицание: «неверно, что …» (стандартная логическая формулировка: «не имеет места, что …»).
  4. Связная формулировка: «неверно, что все студенты посетили Иннополис», то есть есть студенты, которые Иннополис не посещали.
Ответ: Естественный перевод: “Not every student has visited Innopolis.”
4.2. Перевод формулы логики предикатов (Лаба 3, Задание 1.a)

Пусть \(P(x)\) означает «\(x\) любит апельсин» (область — все люди). Переведите \(\neg\exists x\,P(x)\) на естественный английский.

Показать решение
  1. Главная операция: отрицание формулы с квантором существования.
  2. Квантор и предикат: \(\exists x\,P(x)\) — «есть человек, который любит апельсин» / «кто-то любит апельсин».
  3. Отрицание: «неверно, что кто-то любит апельсин».
  4. Эквивалентно: для всех людей \(P(x)\) ложно, то есть \(\forall x\,\neg P(x)\).
Ответ: “No person likes orange.”
4.3. Перевод формулы логики предикатов (Лаба 3, Задание 1.b)

Пусть \(R(x)\) означает «\(x\) знает C++» (область — все люди). Переведите \(\forall x\,\neg R(x)\) на естественный английский.

Показать решение
  1. Квантор: \(\forall x\) — «для каждого человека \(x\) …».
  2. Предикат: \(\neg R(x)\) — «\(x\) не знает C++».
  3. Вместе: «для каждого человека \(x\) верно: \(x\) не знает C++».
Ответ: “No person knows C++.” (вариант: “Everyone does not know C++.”)
4.4. Перевод формулы логики предикатов (Лаба 3, Задание 1.c)

Пусть \(P(x)\) — «\(x\) любит апельсин», \(R(x)\) — «\(x\) знает C++» (область — все люди). Переведите \(\forall x\,(P(x) \rightarrow R(x))\) на естественный английский.

Показать решение
  1. Квантор: \(\forall x\) — «для каждого человека \(x\) …».
  2. Структура: импликация \(P(x) \rightarrow R(x)\) — «если \(P(x)\), то \(R(x)\)».
  3. Вместе: «для каждого человека \(x\): если \(x\) любит апельсин, то \(x\) знает C++».
Ответ: “Every person who likes orange knows C++.”
4.5. Перевод формулы логики предикатов (Лаба 3, Задание 1.d)

Пусть \(P(x)\) — «\(x\) любит апельсин», \(R(x)\) — «\(x\) знает C++» (область — все люди). Переведите \(\forall x\,(P(x) \land R(x))\) на естественный английский.

Показать решение
  1. Квантор: \(\forall x\) — «для каждого человека \(x\) …».
  2. Структура: конъюнкция \(P(x) \land R(x)\) — «\(P(x)\) и \(R(x)\) одновременно».
  3. Вместе: «для каждого человека \(x\): \(x\) любит апельсин и \(x\) знает C++».
Ответ: “Every person likes orange and knows C++.”
4.6. Перевод формулы логики предикатов (Лаба 3, Задание 1.e)

Пусть \(P(x)\) — «\(x\) любит апельсин», \(R(x)\) — «\(x\) знает C++» (область — все люди). Переведите \(\exists x\,(P(x) \lor R(x))\) на естественный английский.

Показать решение
  1. Квантор: \(\exists x\) — «существует человек \(x\) такой, что …».
  2. Структура: дизъюнкция \(P(x) \lor R(x)\).
  3. Вместе: «есть человек \(x\), для которого верно: \(x\) любит апельсин или \(x\) знает C++».
Ответ: “There is a person who likes orange or knows C++.”
4.7. Перевод формулы логики предикатов (Лаба 3, Задание 1.f)

Пусть \(P(x)\) — «\(x\) любит апельсин», \(R(x)\) — «\(x\) знает C++» (область — все люди). Переведите \(\exists x\,(P(x) \land R(x))\) на естественный английский.

Показать решение
  1. Квантор: \(\exists x\) — «существует человек \(x\) такой, что …».
  2. Структура: конъюнкция \(P(x) \land R(x)\).
  3. Вместе: «есть человек \(x\), для которого верно: \(x\) любит апельсин и \(x\) знает C++».
Ответ: “There is a person who likes orange and also knows C++.”
4.8. Истинностное значение (Лаба 3, Задание 2)

Определите истинностное значение утверждения \(\exists x\,(x = 0)\), если область — все вещественные числа.

Показать решение
  1. Смысл формулы: «существует вещественное \(x\) такое, что \(x = 0\)».
  2. Анализ: принадлежит ли число \(0\) множеству \(\mathbb{R}\).
  3. Вывод: \(0 \in \mathbb{R}\), значит подходящее \(x\) существует.
Ответ: утверждение истинно (True).
4.9. Истинностное значение (Лаба 3, Задание 2.a)

Определите истинностное значение утверждения \(\exists x\,(x^3 = -1)\), если область — все вещественные числа.

Показать решение
  1. Смысл: «существует вещественное \(x\) с \(x^3 = -1\)».
  2. Анализ: нужно ли вещественное решение уравнения \(x^3 = -1\).
  3. Пример: \(x = -1\) подходит, так как \((-1)^3 = -1\).
  4. Вывод: в области есть подходящее \(x\).
Ответ: истинно (True).
4.10. Истинностное значение (Лаба 3, Задание 2.b)

Определите истинностное значение утверждения \(\forall x\,(x = -x)\), если область — все вещественные числа.

Показать решение
  1. Смысл: «для каждого вещественного \(x\) верно \(x = -x\)».
  2. Анализ: квантор \(\forall\) требует истинности для всех элементов области; достаточно контрпримера (counterexample).
  3. Контрпример: при \(x = 1\) получаем \(1 = -1\) — ложь.
  4. Вывод: формула ложна на \(\mathbb{R}\).
Ответ: ложно (False).
4.11. Истинностное значение (Лаба 3, Задание 2.c)

Определите истинностное значение утверждения \(\exists x\,\forall y\,(x > y)\), если область — все вещественные числа.

Показать решение
  1. Смысл: «существует вещественное \(x\), большее любого вещественного \(y\)».
  2. Анализ: такого одного «максимального» вещественного числа не существует.
  3. От противного: пусть такое \(x\) есть; возьмём \(y = x + 1\), тогда \(x > x + 1\) неверно.
  4. Вывод: утверждение ложно.
Ответ: ложно (False).
4.12. Истинностное значение (Лаба 3, Задание 2.d)

Определите истинностное значение утверждения \(\forall x\,\exists y\,(x + y = 0)\), если область — все вещественные числа.

Показать решение
  1. Смысл: «для каждого вещественного \(x\) найдётся вещественное \(y\) с \(x + y = 0\)».
  2. Анализ: у каждого вещественного есть аддитивный обратный (additive inverse) в \(\mathbb{R}\).
  3. Проверка: для любого \(x\) подойдёт \(y = -x\); тогда \(x + (-x) = 0\), и \(-x \in \mathbb{R}\).
  4. Вывод: условие выполняется для всех \(x\).
Ответ: истинно (True).
4.13. Переписать отрицание (Лаба 3, Задание 3.a)

Перепишите утверждение \(\neg\exists x\,(x \ge 0)\) так, чтобы отрицание не стояло вне квантора.

Показать решение
  1. Правило для \(\exists\): \(\neg\exists x\,P(x) \equiv \forall x\,\neg P(x)\).
  2. Применение: \(\neg\exists x\,(x \ge 0)\) переходит в \(\forall x\,\neg(x \ge 0)\).
  3. Упрощение: \(\neg(x \ge 0)\) эквивалентно \(x < 0\).
Ответ: \(\forall x\,(x < 0)\).
4.14. Переписать отрицание (Лаба 3, Задание 3.b)

Перепишите утверждение \(\neg\forall x\,(\neg P(x) \lor R(x))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Правило для \(\forall\): \(\neg\forall x\,Q(x) \equiv \exists x\,\neg Q(x)\); получаем \(\exists x\,\neg(\neg P(x) \lor R(x))\).
  2. Закон де Моргана (De Morgan’s law): \(\neg(A \lor B) \equiv (\neg A \land \neg B)\); внутри — \(\exists x\,(\neg(\neg P(x)) \land \neg R(x))\).
  3. Двойное отрицание: \(\neg(\neg P(x)) \equiv P(x)\).
Ответ: \(\exists x\,(P(x) \land \neg R(x))\).
4.15. Переписать отрицание (Лаба 3, Задание 3.c)

Перепишите \(\neg\forall x\,((x > 0) \lor (x < 0))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Квантор: \(\neg\forall x\,\ldots \equiv \exists x\,\neg\ldots\) ⇒ \(\exists x\,\neg((x > 0) \lor (x < 0))\).
  2. Де Морган: \(\exists x\,(\neg(x > 0) \land \neg(x < 0))\).
  3. Предикаты: \(\neg(x > 0) \equiv (x \le 0)\), \(\neg(x < 0) \equiv (x \ge 0)\).
  4. Итог: \(\exists x\,((x \le 0) \land (x \ge 0))\); это выполняется только при \(x = 0\).
Ответ: \(\exists x\,((x \le 0) \land (x \ge 0))\), эквивалентно \(\exists x\,(x = 0)\).
4.16. Переписать отрицание (Лаба 3, Задание 3.d)

Перепишите \(\neg\exists x\,\exists y\,P(x,y)\) так, чтобы отрицание не стояло вне квантора.

Показать решение
  1. Сначала по \(\exists y\): \(\forall x\,\neg(\exists y\,P(x,y))\).
  2. Затем по \(\exists y\) внутри: \(\forall x\,\forall y\,\neg P(x,y)\).
Ответ: \(\forall x\,\forall y\,\neg P(x,y)\).
4.17. Переписать отрицание (Лаба 3, Задание 3.e)

Перепишите \(\neg\forall x\,\exists y\,((x \ge 0) \land (y < 0))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. По внешнему \(\forall\): \(\exists x\,\neg(\exists y\,((x \ge 0) \land (y < 0)))\).
  2. По \(\exists y\): \(\exists x\,\forall y\,\neg((x \ge 0) \land (y < 0))\).
  3. Де Морган: \(\exists x\,\forall y\,(\neg(x \ge 0) \lor \neg(y < 0))\).
  4. Предикаты: \(\exists x\,\forall y\,((x < 0) \lor (y \ge 0))\).
Ответ: \(\exists x\,\forall y\,((x < 0) \lor (y \ge 0))\).
4.18. Переписать отрицание (Лаба 3, Задание 3.f)

Перепишите \(\neg\exists y\,(R(y) \land \forall x\,\neg P(x,y))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Внешний квантор: \(\forall y\,\neg(R(y) \land \forall x\,\neg P(x,y))\).
  2. Де Морган: \(\forall y\,(\neg R(y) \lor \neg(\forall x\,\neg P(x,y)))\).
  3. Внутренний \(\forall\): \(\forall y\,(\neg R(y) \lor \exists x\,\neg(\neg P(x,y)))\).
  4. Двойное отрицание: \(\forall y\,(\neg R(y) \lor \exists x\,P(x,y))\).
Ответ: \(\forall y\,(\neg R(y) \lor \exists x\,P(x,y))\).
4.19. Переписать отрицание (Лаба 3, Задание 3.g)

Перепишите \(\neg\exists y\,(\exists x\,S(x,y) \lor \forall y\,T(x,y))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Внешний квантор: \(\forall y\,\neg(\exists x\,S(x,y) \lor \forall y\,T(x,y))\).
  2. Де Морган: \(\forall y\,(\neg(\exists x\,S(x,y)) \land \neg(\forall y\,T(x,y)))\).
  3. По внутренним кванторам: \(\forall y\,(\forall x\,\neg S(x,y) \land \exists y\,\neg T(x,y))\).
Ответ: \(\forall y\,(\forall x\,\neg S(x,y) \land \exists y\,\neg T(x,y))\).
4.20. Переписать отрицание (Лаба 3, Задание 3.h)

Перепишите \(\neg(\forall x\,\exists y\,((x \neq 0) \land (xy \neq 0)) \lor \exists x\,\forall y\,((x > y) \land (x + y \neq 0)))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Главная дизъюнкция: форма \(\neg(A \lor B)\) даёт \(\neg A \land \neg B\):
    • \(\neg(\forall x\,\exists y\,((x \neq 0) \land (xy \neq 0))) \land \neg(\exists x\,\forall y\,((x > y) \land (x + y \neq 0)))\).
  2. Часть \(\neg A\):
    • \(\neg\forall x\,\exists y\,\ldots \equiv \exists x\,\forall y\,\neg\ldots\);
    • \(\exists x\,\forall y\,\neg((x \neq 0) \land (xy \neq 0)) \equiv \exists x\,\forall y\,(\neg(x \neq 0) \lor \neg(xy \neq 0))\) (De Morgan);
    • упрощение: \(\exists x\,\forall y\,((x = 0) \lor (xy = 0))\).
  3. Часть \(\neg B\):
    • \(\neg\exists x\,\forall y\,\ldots \equiv \forall x\,\exists y\,\neg\ldots\);
    • \(\forall x\,\exists y\,\neg((x > y) \land (x + y \neq 0)) \equiv \forall x\,\exists y\,(\neg(x > y) \lor \neg(x + y \neq 0))\);
    • упрощение: \(\forall x\,\exists y\,((x \le y) \lor (x + y = 0))\).
  4. Объединение конъюнкцией.
Ответ: \((\exists x\,\forall y\,((x = 0) \lor (xy = 0))) \land (\forall x\,\exists y\,((x \le y) \lor (x + y = 0)))\).
4.21. Области для истины и лжи (Лаба 3, Задание 4)

Укажите одну общую область для \(x\), \(y\) и \(z\), на которой \(\forall x\,\forall y\,((x \neq y) \rightarrow \forall z\,((z = x) \lor (z = y)))\) истинна, и другую, на которой она ложна.

Показать решение
  1. Смысл: для любых двух различных \(x\), \(y\) из области каждый \(z\) должен совпадать с \(x\) или с \(y\).
  2. Когда истинно: если в области не больше двух элементов (при одном элементе посылка \(x \neq y\) всегда ложна — импликация истинна «по пустоте» (vacuously true)).
  3. Когда ложно: если в области три и более различных элемента — выберем два как \(x\), \(y\) и третий как \(z\).

Ответ:

  • Где истинно: любое множество из не более чем двух элементов, напр. \(\{0, 1\}\).
  • Где ложно: любое множество из трёх и более элементов, напр. \(\{0, 1, 2\}\).
4.22. Области для истины и лжи (Лаба 3, Задание 4.a)

Укажите общую область, на которой \(\forall x\,\forall y\,(xy \ge x)\) истинна, и другую, на которой она ложна.

Показать решение
  1. Смысл: для любых \(x\), \(y\) из области \(xy \ge x\).
  2. Условие истинности: например, \(\{1, 2, 3, \ldots\}\) (целые \(\ge 1\)): для таких \(x\), \(y\) имеем \(y \ge 1\), откуда \(xy \ge x\).
  3. Условие лжи: на \(\mathbb{R}\) возьмём \(x = 2\), \(y = 0{,}5\): тогда \(xy = 1 < 2\).

Ответ:

  • Где истинно: \(\{1, 2, 3, \ldots\}\) (или другое подходящее конечное/бесконечное множество с нужным свойством).
  • Где ложно: \(\mathbb{R}\).
4.23. Области для истины и лжи (Лаба 3, Задание 4.b)

Укажите общую область, на которой \(\exists x\,\forall y\,(xy = y)\) истинна, и другую, на которой она ложна.

Показать решение
  1. Смысл: найти \(x\) в области такое, что для всех \(y\) из той же области \(xy = y\).
  2. Условие истинности: если \(1\) лежит в области, можно взять \(x = 1\): тогда \(1 \cdot y = y\) для всех \(y\) (например, область \(\mathbb{Z}\)).
  3. Условие лжи: если \(1\) нет в области — например, чётные целые \(\{\ldots, -2, 0, 2, \ldots\}\).

Ответ:

  • Где истинно: \(\mathbb{Z}\) (или любая область, содержащая \(1\)).
  • Где ложно: множество чётных целых.
4.24. Области для истины и лжи (Лаба 3, Задание 4.c)

Укажите общую область, на которой \(\forall x\,\forall y\,\exists z\,(x + y + z = 0)\) истинна, и другую, на которой она ложна.

Показать решение
  1. Смысл: для любых \(x\), \(y\) найти \(z\) в той же области с \(x + y + z = 0\), т.е. \(z = -(x+y)\).
  2. Условие истинности: \(\mathbb{Z}\) или \(\mathbb{R}\) — замкнуты относительно сложения и противоположного элемента.
  3. Условие лжи: \(\mathbb{N} = \{0, 1, 2, \ldots\}\) — при \(x = 1\), \(y = 2\) нужно \(z = -3 \notin \mathbb{N}\).

Ответ:

  • Где истинно: \(\mathbb{R}\).
  • Где ложно: \(\mathbb{N}\) (неотрицательные целые).
4.25. Области для истины и лжи (Лаба 3, Задание 4.d)

Укажите общую область, на которой \(\forall x\,\forall y\,\forall z\,\exists w\,((w \neq x) \land (w \neq y) \land (w \neq z))\) истинна, и другую, на которой она ложна.

Показать решение
  1. Смысл: для любых трёх элементов области (не обязательно различных) найти четвёртый \(w\), отличный от каждого из них.
  2. Условие истинности: на бесконечной области «тройка» никогда не исчерпывает все элементы — например, \(\mathbb{Z}\).
  3. Условие лжи: на конечной области из не более чем трёх элементов — например, \(\{1, 2, 3\}\).

Ответ:

  • Где истинно: любое бесконечное множество, напр. \(\mathbb{Z}\).
  • Где ложно: конечное множество, напр. \(\{1, 2, 3\}\).
4.26. Перевод формулы логики предикатов (Туториал 3, Задание 1)

Область — все студенты; \(P(x)\) — «\(x\) посетил Иннополис». Переведите \(\forall x\,P(x)\) на естественный английский.

Показать решение
  1. Квантор: \(\forall x\) — квантор всеобщности (universal quantifier): «для каждого \(x\)» / «для любого \(x\)».
  2. Предикат: \(P(x)\) — «\(x\) посетил Иннополис».
  3. Вместе: «для каждого студента \(x\): \(x\) посетил Иннополис».
Ответ: “Every student has visited Innopolis.”
4.27. Перевод формулы логики предикатов (Туториал 3, Задание 2)

Те же область и \(P(x)\). Переведите \(\neg\forall x\,P(x)\) на естественный английский.

Показать решение
  1. Главная операция: отрицание формулы \(\forall x\,P(x)\).
  2. Внутренняя часть: \(\forall x\,P(x)\) — «каждый студент посетил Иннополис».
  3. Отрицание: «неверно, что каждый студент посетил Иннополис».
  4. Эквивалентно: существует студент, не посетивший Иннополис: \(\exists x\,\neg P(x)\).
Ответ: “Not every student has visited Innopolis.” или “Some students have not visited Innopolis.”
4.28. Перевод формулы логики предикатов (Туториал 3, Задание 3)

Те же область и \(P(x)\). Переведите \(\forall x\,\neg P(x)\) на естественный английский.

Показать решение
  1. Квантор: \(\forall x\) — «для каждого \(x\) …».
  2. Предикат: \(\neg P(x)\) — «\(x\) не посетил Иннополис».
  3. Вместе: «каждый студент не посетил Иннополис».
Ответ: “No student has visited Innopolis.”
4.29. Перевод формулы логики предикатов (Туториал 3, Задание 4)

Область — все студенты; \(P(x)\) — «\(x\) сообразительный» (smart). Переведите \(\exists x\,P(x)\) на естественный английский.

Показать решение
  1. Квантор: \(\exists x\) — квантор существования (existential quantifier): «существует \(x\) …».
  2. Предикат: \(P(x)\) — «\(x\) сообразительный».
  3. Вместе: «есть студент \(x\), который сообразительный».
Ответ: “Some student is smart.” или “There is at least one smart student.”
4.30. Перевод формулы логики предикатов (Туториал 3, Задание 5)

Те же область и \(P(x)\). Переведите \(\neg\exists x\,P(x)\) на естественный английский.

Показать решение
  1. Главная операция: отрицание \(\exists x\,P(x)\).
  2. Внутренняя часть: «есть сообразительный студент».
  3. Отрицание: «неверно, что есть сообразительный студент».
  4. Эквивалентно: \(\forall x\,\neg P(x)\).
Ответ: “No student is smart.”
4.31. Перевод формулы логики предикатов (Туториал 3, Задание 6)

Те же область и \(P(x)\). Переведите \(\exists x\,\neg P(x)\) на естественный английский.

Показать решение
  1. Квантор: \(\exists x\) — «существует \(x\) …».
  2. Предикат: \(\neg P(x)\) — «\(x\) не сообразительный».
  3. Вместе: «есть студент, который не сообразительный».
Ответ: “Some student is not smart.”
4.32. Перевод формулы логики предикатов (Туториал 3, Задание 7)

Область — \(\mathbb{N}\); \(P(x)\) — «\(x\) чётное», \(R(x)\) — «\(x\) простое». Переведите \(\exists x\,(P(x) \land R(x))\) на естественный английский.

Показать решение
  1. Квантор: \(\exists x\) — «существует натуральное \(x\) …».
  2. Предикаты: \(P(x) \land R(x)\) — «\(x\) чётное и простое».
  3. Вместе: «существует натуральное \(x\), чётное и простое».
Ответ: “There exists an even prime number.” (утверждение истинно: подходит \(2\).)
4.33. Истинностное значение (Туториал 3, Задание 8)

Область — \(\mathbb{R}\). Определите истинностное значение \(\exists x\,(x = 0)\).

Показать решение
  1. Смысл: «существует вещественное \(x\) с \(x = 0\)».
  2. Проверка: \(0 \in \mathbb{R}\).
  3. Вывод: подходящее \(x\) есть.
Ответ: истинно (True).
4.34. Истинностное значение (Туториал 3, Задание 9)

Область — \(\mathbb{R}\). Определите истинностное значение \(\forall x\,(x + 1 = x + 2)\).

Показать решение
  1. Смысл: «для всех вещественных \(x\) верно \(x + 1 = x + 2\)».
  2. Анализ: из \(x + 1 = x + 2\) следует \(1 = 2\) — противоречие.
  3. Вывод: ни для одного \(x\) равенство не выполняется, тем более не для всех.
Ответ: ложно (False).
4.35. Истинностное значение (Туториал 3, Задание 10)

Область — \(\mathbb{R}\). Определите истинностное значение \(\forall x\,\forall y\,(x + y = y + x)\).

Показать решение
  1. Смысл: коммутативность сложения на \(\mathbb{R}\).
  2. Факт: для вещественных \(x + y = y + x\) всегда.
  3. Вывод: формула истинна на \(\mathbb{R}\).
Ответ: истинно (True).
4.36. Истинностное значение (Туториал 3, Задание 11)

Область — \(\mathbb{Z}\). Определите истинностное значение \(\exists x\,\exists y\,(x + y = xy)\).

Показать решение
  1. Смысл: «существуют целые \(x\), \(y\) с \(x + y = xy\)».
  2. Поиск примера: достаточно одной подходящей пары.
  3. Подстановки:
    • \(x = 0\): уравнение \(0 + y = 0 \cdot y\) даёт \(y = 0\) — пара \((0,0)\).
    • \(x = 2\): \(2 + y = 2y\) даёт \(y = 2\) — пара \((2,2)\).
  4. Вывод: существует хотя бы одна пара.
Ответ: истинно (True).
4.37. Истинностное значение (Туториал 3, Задание 12)

Область — \(\mathbb{R}\). Определите истинностное значение \(\forall x\,\forall y\,\forall z\,(x + yz = xy + z)\).

Показать решение
  1. Смысл: тождество \(x + yz = xy + z\) для всех вещественных \(x,y,z\).
  2. Контрпример: достаточно одного набора значений.
  3. Проверка: \(x = 1\), \(y = 2\), \(z = 3\): слева \(1 + 2 \cdot 3 = 7\), справа \(1 \cdot 2 + 3 = 5\).
  4. Вывод: формула ложна.
Ответ: ложно (False).
4.38. Переписать отрицание (Туториал 3, Задание 13)

Перепишите \(\neg\exists x\,(x \neq 0)\) так, чтобы отрицание не стояло вне квантора.

Показать решение
  1. Правило: \(\neg\exists x\,P(x) \equiv \forall x\,\neg P(x)\).
  2. Здесь \(P(x)\) — это \((x \neq 0)\).
  3. Шаг: \(\forall x\,\neg(x \neq 0)\).
  4. Упрощение: \(\neg(x \neq 0) \equiv (x = 0)\).
Ответ: \(\forall x\,(x = 0)\).
4.39. Переписать отрицание (Туториал 3, Задание 14)

Перепишите \(\neg\forall x\,(x \ge 0)\) так, чтобы отрицание не стояло вне квантора.

Показать решение
  1. Правило: \(\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)\).
  2. Здесь \(P(x)\) — \((x \ge 0)\).
  3. Шаг: \(\exists x\,\neg(x \ge 0)\).
  4. Упрощение: \(\neg(x \ge 0) \equiv (x < 0)\).
Ответ: \(\exists x\,(x < 0)\).
4.40. Переписать отрицание (Туториал 3, Задание 15)

Перепишите \(\neg\forall x\,\exists y\,(x > y)\) так, чтобы отрицание не стояло вне квантора.

Показать решение
  1. Сначала \(\neg\forall x\): \(\exists x\,\neg(\exists y\,(x > y))\).
  2. Затем \(\neg\exists y\): \(\exists x\,\forall y\,\neg(x > y)\).
  3. Упрощение: \(\neg(x > y) \equiv (x \le y)\).
Ответ: \(\exists x\,\forall y\,(x \le y)\).
4.41. Переписать отрицание (Туториал 3, Задание 16)

Перепишите \(\neg\forall x\,((x > 0) \land (x < 100))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Правило для \(\forall\): \(\exists x\,\neg((x > 0) \land (x < 100))\).
  2. Де Морган: \(\exists x\,(\neg(x > 0) \lor \neg(x < 100))\).
  3. Предикаты: \((x \le 0) \lor (x \ge 100)\).
Ответ: \(\exists x\,((x \le 0) \lor (x \ge 100))\).
4.42. Переписать отрицание (Туториал 3, Задание 17)

Перепишите \(\neg\exists x\,\neg P(x)\) так, чтобы отрицание не стояло вне квантора.

Показать решение
  1. Правило: \(\neg\exists x\,Q(x) \equiv \forall x\,\neg Q(x)\) с \(Q(x) = \neg P(x)\).
  2. Шаг: \(\forall x\,\neg(\neg P(x))\).
  3. Двойное отрицание: \(\forall x\,P(x)\).
Ответ: \(\forall x\,P(x)\).
4.43. Переписать отрицание (Туториал 3, Задание 18)

Перепишите \(\neg\forall x\,(\neg P(x) \lor R(x))\) так, чтобы отрицание не стояло вне квантора или логической связки.

Показать решение
  1. Правило для \(\forall\): \(\exists x\,\neg(\neg P(x) \lor R(x))\).
  2. Де Морган: \(\exists x\,(P(x) \land \neg R(x))\) после \(\neg(\neg P(x)) \equiv P(x)\).
Ответ: \(\exists x\,(P(x) \land \neg R(x))\).
4.44. Области для истины и лжи (Туториал 3, Задание 19)

Укажите область для переменной \(x\), на которой \(\exists x\,(x = 0)\) истинно, и другую, на которой ложно.

Показать решение
  1. Условие истинности: в области должен быть элемент \(0\).
  2. Условие лжи: в области нет \(0\).
  3. Примеры:
    • Где истинно: \(\mathbb{Z}\), \(\{-1,0,1\}\), \(\mathbb{R}\).
    • Где ложно: \(\mathbb{Z}^+ = \{1,2,3,\ldots\}\), отрицательные целые без нуля.

Ответ:

  • Где истинно: \(\mathbb{R}\).
  • Где ложно: \(\mathbb{Z}^+\) (строго положительные целые).
4.45. Области для истины и лжи (Туториал 3, Задание 20)

Укажите область для \(x\), на которой \(\forall x\,(x > 0)\) истинно, и другую, на которой ложно.

Показать решение
  1. Условие истинности: каждый элемент области \(> 0\).
  2. Условие лжи: есть элемент \(\le 0\).
  3. Примеры:
    • Где истинно: \(\{1,2,3,\ldots\}\), \(\mathbb{R}^+ = (0,\infty)\).
    • Где ложно: \(\mathbb{Z}\), \(\mathbb{R}\) (есть \(0\) и отрицательные).

Ответ:

  • Где истинно: \(\mathbb{R}^+\).
  • Где ложно: \(\mathbb{R}\).
4.46. Области для истины и лжи (Туториал 3, Задание 21)

Укажите область для \(x\) и \(y\), на которой \(\forall x\,\forall y\,(xy > 0)\) истинно, и другую, на которой ложно.

Показать решение
  1. Условие истинности: произведение любых двух элементов (включая квадрат одного) положительно — так, если все элементы строго положительны или все строго отрицательны.
  2. Условие лжи: есть пара с произведением \(\le 0\) — например, если в области есть \(0\) или есть и положительные, и отрицательные числа.
  3. Примеры:
    • Где истинно: \(\{1,2,3,\ldots\}\).
    • Где ложно: \(\mathbb{Z}\) (напр. \(2 \cdot (-3) < 0\), \(5 \cdot 0 = 0\)).

Ответ:

  • Где истинно: \(\mathbb{Z}^+\).
  • Где ложно: \(\mathbb{Z}\).
4.47. Области для истины и лжи (Туториал 3, Задание 22)

Укажите область для \(x\) и \(y\), на которой \(\exists x\,\exists y\,(x + y > 0)\) истинно, и другую, на которой ложно.

Показать решение
  1. Условие истинности: найдётся пара с положительной суммой.
  2. Условие лжи: сумма любых двух элементов \(\le 0\).
  3. Примеры:
    • Где истинно: \(\mathbb{Z}\) (\(2 + 3 = 5 > 0\)).
    • Где ложно: \(\{-1,-2,-3,\ldots\}\).

Ответ:

  • Где истинно: \(\mathbb{Z}\).
  • Где ложно: строго отрицательные целые (\(\mathbb{Z}^-\) в смысле \(\{-1,-2,\ldots\}\)).
4.48. Области для истины и лжи (Туториал 3, Задание 23)

Укажите область для \(x\) и \(y\), на которой \(\exists x\,\forall y\,(x = y)\) истинно, и другую, на которой ложно.

Показать решение
  1. Условие истинности: «один \(x\) равен каждому \(y\)» возможно только если в области ровно один элемент.
  2. Условие лжи: в области не меньше двух различных элементов.
  3. Примеры:
    • Где истинно: \(\{5\}\) (любое одноэлементное множество).
    • Где ложно: \(\{5,6\}\), \(\mathbb{Z}\).

Ответ:

  • Где истинно: \(\{1\}\) (любое одноэлементное множество \(\{a\}\)).
  • Где ложно: \(\mathbb{Z}\).
4.49. Области для истины и лжи (Туториал 3, Задание 24)

Укажите область для \(x\) и \(y\), на которой \(\forall x\,((x \neq 0) \rightarrow \exists y\,(xy = 1))\) истинно, и другую, на которой ложно.

Показать решение
  1. Условие истинности: у каждого ненулевого \(x\) есть мультипликативный обратный (multiplicative inverse) в той же области — например поле (field) \(\mathbb{Q}\) или \(\mathbb{R}\).
  2. Условие лжи: найдётся ненулевой \(x\) без обратного в области — напр. в \(\mathbb{Z}\) для \(x = 2\) нужно \(y = 1/2 \notin \mathbb{Z}\).
  3. Примеры:
    • Где истинно: \(\mathbb{R}\) (или \(\mathbb{Q}\)).
    • Где ложно: \(\mathbb{Z}\).

Ответ:

  • Где истинно: \(\mathbb{R}\).
  • Где ложно: \(\mathbb{Z}\).
4.50. Области для истины и лжи (Туториал 3, Задание 25)

Укажите одну общую область для \(x\), \(y\) и \(z\), на которой \(\forall x\,\forall y\,((x \neq y) \rightarrow \forall z\,((z = x) \lor (z = y)))\) истинна, и другую, на которой ложна.

Показать решение
  1. Условие истинности: в области не больше двух элементов (см. разбор в задании 4.21).
  2. Условие лжи: не меньше трёх различных элементов.
  3. Примеры:
    • Где истинно: \(\{0,1\}\) или любое \(\{a,b\}\).
    • Где ложно: \(\{0,1,2\}\) или \(\mathbb{Z}\).

Ответ:

  • Где истинно: \(\{a,b\}\) (два различных элемента).
  • Где ложно: \(\mathbb{Z}\).